//
// Description: 142. 环形链表 II
// Created by Loading on 2022/7/17.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

/* Floyd 判圈算法 */
ListNode *detectCycle(ListNode *head) {
    if (!head || !head->next) {
        return nullptr;
    }

    auto fast = head;
    auto slow = head;
    do {
        slow = slow->next;
        fast = fast->next->next;
        if (!fast || !fast->next) {
            return nullptr;
        }
    } while (slow != fast);

    // 存在环，将其中一个指针移动到头，与另一指针同时移动，相遇位置即为环入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

int main() {
    auto head = new ListNode(3);
    auto circle = head->next = new ListNode(2);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(-4);
    head->next->next->next->next = circle;

    auto res = detectCycle(head);

    if (res) {
        cout << res->val << endl;
    } else {
        cout << "no circle" << endl;
    }

    return 0;
}